/*
 *  LZ4K Compressor by Vovo
 */
#include <linux/lz4k.h>
#include <linux/types.h>

unsigned short lz4k_matchlen_encode[32] =
{ 0, 0, 0, 1024,  1026,  2049,  2053,  2057,  2061,  3091,  3123,  3083,  2563,  3643,  3707,  3115,  3099,  4119,  3591,  4247,  3655,  4791,  4183,  4311,  3623,  5047,  4727,  4983,  3687,  4855,  5111,  4151,  };

unsigned short lz4k_matchoff_encode[32] =
{ 1024,  1032,  1292,  1028,  1554,  1308,  1586,  1546,  1578,  1562,  1830,  1594,  1894,  1282,  1814,  1542,  2158,  1878,  2286,  1846,  2078,  1910,  2206,  1806,  2142,  2270,  2110,  1870,  2238,  1838,  2174,  2302,  };

unsigned short lz4k_literallen_encode[18] =
{0,  128,  385,  517,  525,  515,  651,  775,  807,  667,  919,  983,  951,  1015,  911,  975,  943,  1007,  };

unsigned short lz4k_literalch_encode[256] =
{ 2048,  3092,  3596,  3660,  3628,  4154,  4282,  4218,  3692,  3612,  3676,  4346,  4102,  4230,  4166,  4294,  3644,  4134,  4262,  4198,  4326,  4861,  5117,  4611,  4118,  4867,  4246,  4182,  4310,  4150,  4278,  4214,  3124,  4342,  4110,  4238,  4174,  4302,  4739,  4995,  3708,  4142,  4675,  4931,  4270,  4803,  4206,  4334,  3586,  4126,  4254,  4190,  4318,  5059,  4643,  4899,  4158,  4771,  5027,  4707,  4963,  4835,  5091,  4627,  2564,  3650,  4286,  4222,  4350,  4883,  4755,  5011,  4097,  4691,  4947,  4225,  4161,  4289,  4129,  4257,  3618,  3682,  4193,  4321,  4113,  4819,  5075,  4659,  4241,  4915,  4787,  5043,  4723,  4979,  4851,  4177,  4305,  3602,  4145,  4273,  4209,  3666,  4337,  4105,  4233,  3634,  5107,  4619,  4169,  4297,  3698,  3594,  3658,  4137,  3626,  4265,  3690,  4201,  4329,  4875,  4121,  4249,  4747,  5003,  4683,  4939,  4811,  5067,  3610,  4651,  4907,  4779,  4185,  5035,  4715,  4971,  4313,  4843,  5099,  4635,  4891,  4763,  5019,  4699,  4153,  4955,  4827,  5083,  4667,  4923,  4795,  5051,  4281,  4731,  4987,  4859,  5115,  4615,  4871,  4743,  4217,  4999,  4679,  4935,  4807,  5063,  4647,  4903,  4345,  4775,  5031,  4711,  4967,  4839,  5095,  4631,  4101,  4887,  4759,  5015,  4229,  4695,  4951,  4823,  4165,  5079,  4663,  4919,  4293,  4791,  5047,  4727,  4133,  4983,  4855,  5111,  4623,  4879,  4751,  5007,  4261,  4687,  4943,  4815,  5071,  4655,  4911,  4783,  4197,  4325,  4117,  4245,  4181,  4309,  5039,  4719,  4149,  4975,  4847,  5103,  4639,  4895,  4767,  5023,  3674,  4277,  4703,  4213,  4959,  4341,  4831,  5087,  4109,  4671,  4927,  4799,  4237,  4173,  4301,  5055,  4141,  4269,  4205,  4333,  4125,  4253,  4735,  4189,  4317,  4157,  4285,  4991,  4221,  4863,  5119,  2056,  };

#define RESERVE_16_BITS() \
if (bitstobeoutput >= 16) { \
    *( (unsigned short *)op) = (unsigned short) (bits_buffer32 & 0xffff); \
    op += 2; \
    bits_buffer32 = bits_buffer32 >> 16; \
    bitstobeoutput -= 16; \
}

#define STORE_BITS(bits, code) \
    bits_buffer32 |= (code) << bitstobeoutput; \
    bitstobeoutput += (bits);

static size_t
_lz4k_do_compress(const unsigned char *in, size_t in_len,
    unsigned char *out, size_t *out_len, void *wrkmem)
{
    const unsigned char *ip = in;
    unsigned char *op = out;
    const unsigned char * const in_end = in + in_len;
    const unsigned char * const ip_end = in + in_len - 3;
    const unsigned char *ii = ip;
    const unsigned char ** const dict = wrkmem;
    unsigned int bitstobeoutput = 0;
    unsigned int bits_buffer32 = 0;

    bitstobeoutput = 1;

    for (;;)
    {
        const unsigned char *m_pos;
        {
            size_t dindex;
            unsigned int ip_content = *(unsigned int*)ip;
            unsigned int hash_temp = ip_content ^ (ip_content >> 12);
            dindex = hash_temp & 0xfff;
            m_pos = dict[dindex];
            dict[dindex] = ip;

            if (m_pos < in || m_pos >= ip || ( (*(unsigned int*)m_pos << 8) != (ip_content << 8) ) ) {
                ++ip;
                dindex = (hash_temp >> 8) & 0xfff;
                m_pos = dict[dindex];
                dict[dindex] = ip;
                if (m_pos < in || m_pos >= ip || ( (*(unsigned int*)m_pos << 8) != (ip_content & 0xffffff00) ) ) {
                    ++ip;
                    if (__builtin_expect(!!(ip >= ip_end), 0) )
                        break;
                    continue;
                }
            }
        }

        {
            size_t lit = ip - ii;

            if (lit > 0) {
                if (lit == 1) {
                    int value, bits, code;
                    RESERVE_16_BITS();
                    value = lz4k_literalch_encode[*ii++];
                    bits = value >> 9;
                    code = (value & 0x1ff) << 2;
                    STORE_BITS(bits + 2, code);
                } else if (lit == 2) {
                    int value, bits, code;
                    int value2, bits2, code2;
                    RESERVE_16_BITS();
                    if (bitstobeoutput > (32 - 22) ) {
                        *op++ = (unsigned char) (bits_buffer32 & 0xff);
                        bits_buffer32 = bits_buffer32 >> 8;
                        bitstobeoutput -= 8;
                    }
                    value = lz4k_literalch_encode[*ii++];
                    bits = value >> 9;
                    code = value & 0x1ff;
                    value2 = lz4k_literalch_encode[*ii++];
                    bits2 = value2 >> 9;
                    code2 = value2 & 0x1ff;
                    bits_buffer32 |= ( ( ( (code2 << bits) | code) << 4) | 2) << bitstobeoutput;
                    bitstobeoutput += bits2 + bits + 4;
                } else {
                    if (lit <= 17) {
                        int value, bits, code;
                        RESERVE_16_BITS();
                        value = lz4k_literallen_encode[lit];
                        bits = value >> 7;
                        code = (value & 0x7f) << 1;
                        STORE_BITS(bits + 1, code);
                    } else {
                        int code = ( (lit - 1) << 6) | 0x3e;

                        RESERVE_16_BITS();
                        if (bitstobeoutput > (32 - 18) ) {
                            *op++ = (unsigned char) (bits_buffer32 & 0xff);
                            bits_buffer32 = bits_buffer32 >> 8;
                            bitstobeoutput -= 8;
                        }
                        STORE_BITS(17 + 1, code);
                    }

                    while (1) {
                        while (bitstobeoutput < 24) {
                            int value, bits, code;
                            value = lz4k_literalch_encode[*ii++];
                            bits = value >> 9;
                            code = value & 0x1ff;
                            STORE_BITS(bits, code);
                            if (__builtin_expect(!!(ii == ip), 0) ) {
                                goto break_literal_1;
                            }
                        }
                        *( (unsigned int *)op) = bits_buffer32;
                        op += 3;
                        bits_buffer32 = bits_buffer32 >> 24;
                        bitstobeoutput -= 24;
                    }
                }
            }
            else {
                if (bitstobeoutput == 32) {
                    *( (unsigned int *)op) = bits_buffer32;
                    op += 4;
                    bits_buffer32 = 1;
                    bitstobeoutput = 1;
                } else {
                    bits_buffer32 |= 1 << bitstobeoutput;
                    bitstobeoutput += 1;
                }
            }
        }

break_literal_1:

        m_pos += 3;
        ip += 3;

        if (__builtin_expect(!!(ip < in_end), 1) && *m_pos == *ip) {
            m_pos++, ip++;
            while (__builtin_expect(!!(ip < (in_end-1) ), 1) && *(unsigned short*)m_pos == *(unsigned short*)ip)
                m_pos += 2, ip += 2;
            if (__builtin_expect(!!(ip < in_end), 1) && *m_pos == *ip)
                m_pos += 1, ip += 1;
        }

        RESERVE_16_BITS();

        {
            size_t m_off = ip - m_pos;
            if ( (m_off & 3) == 0 && m_off <= 128) {
                int value = lz4k_matchoff_encode[ (m_off / 4) - 1];
                int bits = value >> 8;
                int code = value & 0xff;
                STORE_BITS(bits, code);
            } else {
                int code = (m_off << 1) | 0x1;
                STORE_BITS(13, code);
            }
        }
        RESERVE_16_BITS();

        {
            size_t m_len = ip - ii;
            if (m_len < 32) {
                int value = lz4k_matchlen_encode[m_len];
                int bits = value >> 9;
                int code = value & 0x1ff;
                STORE_BITS(bits, code);
            } else {
                int code = (m_len << 4) | 0xf;
                STORE_BITS(16, code);
            }
        }

        ii = ip;
        if (__builtin_expect(!!(ip >= ip_end), 0) )
            break;
    }

    if ( (in_end - ii) > 0)
    {
        size_t t = in_end - ii;
        if (t == 1) {
            int value, bits, code;
            RESERVE_16_BITS();
            value = lz4k_literalch_encode[*ii++];
            bits = value >> 9;
            code = (value & 0x1ff) << 2;
            bits_buffer32 |= code << bitstobeoutput;
            bitstobeoutput += bits + 2;
        } else {
            while (bitstobeoutput >= 8) {
                *op++ = (unsigned char) (bits_buffer32 & 0xff);
                bits_buffer32 = bits_buffer32 >> 8;
                bitstobeoutput -= 8;
            }
            bitstobeoutput += 1;

            if (t <= 17) {
                int value = lz4k_literallen_encode[t];
                int bits = value >> 7;
                int code = value & 0x7f;
                bits_buffer32 |= code << bitstobeoutput;
                bitstobeoutput += bits;
            } else {
                int code = ( (t - 1) << 5) | 0x1f;
                bits_buffer32 |= code << bitstobeoutput;
                bitstobeoutput += 17;
            }

            while (1) {
                while (bitstobeoutput < 24) {
                    int value, bits, code;
                    value = lz4k_literalch_encode[*ii++];
                    bits = value >> 9;
                    code = value & 0x1ff;
                    bits_buffer32 |= code << bitstobeoutput;
                    bitstobeoutput += bits;
                    if (__builtin_expect(!!(--t == 0), 0) )
                        goto break_literal_2;
                }
                *( (unsigned int *)op) = bits_buffer32;
                op += 3;
                bits_buffer32 = bits_buffer32 >> 24;
                bitstobeoutput -= 24;
            }
        }
    }

break_literal_2:
    while (bitstobeoutput >= 8) {
        *op++ = (unsigned char) (bits_buffer32 & 0xff);
        bits_buffer32 = bits_buffer32 >> 8;
        bitstobeoutput -= 8;
    }
    if (bitstobeoutput != 0) {
        *op++ = (unsigned char) (bits_buffer32 & 0xff);
    }

    *( (unsigned int *)op) = LZ4K_TAG;
    op += 4;

    *out_len = op - out;

    return 0;
}

int lz4k_compress(const unsigned char *in, size_t in_len, unsigned char *out,
        size_t *out_len, void *wrkmem)
{
    unsigned char *op = out;

    if (in_len > 4096) {
        return -1;
    }

    if (__builtin_expect(!!(in_len == 0), 0) ) {
        *out_len = 0;
        return -1;
    } else {
        _lz4k_do_compress(in, in_len, op, out_len, wrkmem);
    }

    if (*out_len <= 0) {
        return -1;
    }

    return 0;
}

